package everyday;

/**
 * @author zhangmin
 * @create 2022-05-05 10:16
 * 剑指 Offer 43. 1～n 整数中 1 出现的次数
 * 输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
 * 例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
 *
 * 思路：
 * 将n的十进制数划分成当前位cur、高位high、低位low。然后遍历每一位是cur，对cur来说，可以计算出在这一位上能出现的1的个数
 * cur==0:则这一位上出现1的个数只和高位有关，也就是高位有多大就有多少的1，因为高位每增加1个，都会在当前位遍历完0-9，则会出现1个1
 * cur==1:和高位和低位都有关，并且当前位会多了一个。和低位有关是因为，当前位为1，怎会遍历所有的低位来搭配这个1
 * 其他：只和高位有关
 */
public class countDigitOne_offer43 {
    public int countDigitOne(int n) {
        int cur=n%10,digit=1,low=0,high=n/10;
        long count =0L;
        while (cur!=0||high!=0){
            if (cur==0){
                count+=high*digit;
            }else if (cur==1){
                count+=(high*digit+low+1);
            }else {
                count+=(high+1)*digit;
            }
            low=cur*digit+low;
            cur=high%10;
            high=high/10;
            digit*=10;
        }
        return (int) count;
    }
}
